#include "common.h"

vector<vector<int>> fourSum(vector<int>& nums, int target)
{
	vector<vector<int>> ans;
	sort(nums.begin(), nums.end());
	int n = nums.size();
	if (n < 4) return ans;
	for (int i = n - 1; i >= 3;)
	{
		long long m = target - nums[i];
		for (int j = i - 1; j >= 2;)
		{
			long long p = m - nums[j];
			int l = 0;
			int r = j - 1;
			while (l < r)
			{
				int k = nums[r] + nums[l];
				if (k == p)
				{
					ans.push_back({ nums[i], nums[j], nums[r], nums[l] });
					r--;
					while (l < r && nums[r] == nums[r + 1]) r--;
					l++;
					while (l < r && nums[l] == nums[l - 1]) l++;
				}
				else if (k < p)
				{
					l++;
					while (l < r && nums[l] == nums[l - 1]) l++;
				}
				else
				{
					r--;
					while (l < r && nums[r] == nums[r + 1]) r--;
				}
			}
			j--;
			while (j >= 2 && nums[j] == nums[j + 1]) j--;
		}
		i--;
		while (i >= 3 && nums[i] == nums[i + 1]) i--;
	}
	return ans;
}